home *** CD-ROM | disk | FTP | other *** search
/ Pascal Super Library / Pascal Super Library (CW International)(1997).bin / COMM / RPL60 / RPL.DOC next >
Text File  |  1986-02-28  |  16KB  |  408 lines
  1.             ----------------------------------------
  2.             TurboPower Utilities Programmer's Manual
  3.                            RPL Utility
  4.             ----------------------------------------
  5.              Copyright (C) 1985 TurboPower Software. 
  6.                       All Rights Reserved.
  7.  
  8.  
  9. 1. Introduction
  10.  
  11. RPL is based on the pattern matching algorithms presented in the 
  12. book "Software Tools in Pascal". However, we have significantly 
  13. extended the capabilities of the tools presented there, and have 
  14. also used more of the powerful data structures available in 
  15. Pascal to improve the performance of the program.
  16.  
  17. We are very interested in hearing of any general purpose 
  18. match/replace expressions that you develop using RPL. 
  19.  
  20.  
  21. 2. Algorithms
  22.  
  23. For a basic introduction to regular expressions or pattern 
  24. matching algorithms we direct you to the references given in 
  25. section 6.
  26.  
  27. RPL uses a record and pointer-based approach to storing regular 
  28. expressions. The following type declarations are key to all of 
  29. the operations of RPL.
  30.  
  31.   TYPE
  32.     longstring = string[255];
  33.  
  34.     tokens = (tnil, tlitchar, tccl, tnccl, tclosure, tmaybeone,
  35.               tany, tbol, teol, tgroup, tbtag, tetag, tditto);
  36.  
  37.     patptr = ^patrecord;
  38.  
  39.     sptr = ^longstring;
  40.  
  41.     patrecord = RECORD
  42.                   tok : tokens;
  43.                   one : Char;
  44.                   nextok : Boolean;
  45.                   strptr : sptr;
  46.                   nestptr, next : patptr;
  47.                 END;
  48.  
  49. Each regular expression used by RPL is stored internally as a 
  50. linked list of PATRECORDs. The function of each record is 
  51. described by the .TOK field of the record. The most 
  52. straightforward function for one of these records is the TLITCHAR 
  53. token type. This indicates that the record will match a single 
  54. literal character, and that character is stored in the .ONE field 
  55. of the record. The record fields perform the following functions:
  56.  
  57.    TOK - a scalar type that classifies the function of this 
  58.          regular expression token.
  59.  
  60.    ONE - a single character, only used when the token matches a 
  61.          single literal character.
  62.  
  63.    NEXTOK - a boolean flag. If true, indicates that this token is 
  64.          part of a chain of alternates. A match to any one of the 
  65.          alternates is acceptable, and once a match is found the 
  66.          succeeding alternates are skipped over.
  67.  
  68.    STRPTR - a pointer to a text string kept on the heap. The text 
  69.          string will hold a character class, which is a list of 
  70.          characters. The record token will be matched if any one 
  71.          of the characters is found.
  72.  
  73.    NESTPTR - This pointer points to a sub-list of the main 
  74.          regular expression. RPL uses these sub-lists to support 
  75.          nesting of regular expressions. Because the sub-lists 
  76.          themselves are composed of the PATRECORD record type, they 
  77.          may also have sub-lists and therefore nesting may occur 
  78.          to arbitrary depth.
  79.  
  80.    NEXT - points to the next record in the linked list of match 
  81.          tokens.
  82.  
  83. The linked list representing a regular expression is terminated 
  84. by a NEXT field containing NIL.
  85.  
  86. The .TOK field can take on any of 13 values. A brief description 
  87. of each of these values follows:
  88.  
  89.    TNIL - used as a place holder to start new linked lists, and 
  90.          occasionally within a list. Performs no matching 
  91.          function, and is simply skipped over during pattern 
  92.          processing.
  93.  
  94.    TLITCHAR - indicates that the token matches a single literal 
  95.          character, contained in the .ONE field.
  96.  
  97.    TCCL - denotes a character class. The match token matches any 
  98.          single character from the string pointed to by the field 
  99.          .STRPTR.
  100.  
  101.    TNCCL - denotes a negative character class. Matches any 
  102.          character NOT contained in the string pointed to by the 
  103.          field .STRPTR.
  104.  
  105.    TCLOSURE - indicates that the token is a "0 or more" closure. 
  106.          The preceding token in the linked list is matched as 
  107.          many times as possible. A "1 or more" closure is created 
  108.          simply by preceding the TCLOSURE token by two copies of 
  109.          the token to be matched.
  110.  
  111.    TMAYBEONE - indicates that the token is a "0 or 1" closure. 
  112.          The preceding token in the linked list is matched either 
  113.          0 or 1 times.
  114.  
  115.    TANY - the token matches any single character.
  116.  
  117.    TBOL - the token matches only at the beginning of a text line.
  118.  
  119.    TEOL - the token matches only at the end of a text line.
  120.  
  121.    TGROUP - indicates that a nested group of tokens follows. A 
  122.          sublist started by the .NESTPTR field is processed 
  123.          before returning to processing of the current list.
  124.  
  125.    TBTAG - indicates that a "tagged match field" is starting. 
  126.          Performs no matching or grouping function.
  127.  
  128.    TETAG - the end of a "tagged match field."
  129.  
  130.    TDITTO - used in replace expressions only. The .ONE field will 
  131.          contain an integer from 0 to 9 indicating which of the 
  132.          tagged match words is to be inserted into the output 
  133.          text.
  134.  
  135. In outline, RPL works as follows:
  136.  
  137. The text version of the match and replace regular expressions is 
  138. read from the command line, a specified file, or from a prompt. 
  139. These regular expressions are checked for syntax, and linked 
  140. lists of the tokens just described are built to represent the 
  141. expressions.
  142.  
  143. The input and output text files are opened, and the input file is 
  144. read one line at a time. Depending on what regular expressions 
  145. and options are specified, each input line may be processed up to 
  146. three separate times using different regular expressions each 
  147. time. The control flow for the various options becomes apparent 
  148. in the routine PROCESSLINE.
  149.  
  150. A match expression processes the line by picking a start location 
  151. (the first character) within that line. It then compares the line 
  152. character by character against the match linked list. If it makes 
  153. it all the way through the linked list without a mismatch, it has 
  154. found a match. If not, it will increment its start position by 
  155. one character and try the linked list again until the start 
  156. position reaches the end of the line. From these operations 
  157. alone, the algorithm may need to do order of n*m high level 
  158. comparisons per line, where n is the number of characters in the 
  159. line and m the number of characters in the pattern.
  160.  
  161. If the match expression contains a closure (like a * wildcard), 
  162. the processing requirements may increase by another factor of n. 
  163. The reference by Allen Holub describes this effect quite well.
  164.  
  165. A replace expression needs to repeat these operations, with some 
  166. additional work. When the replace expression matches a character, 
  167. it sets a flag for that position of the input text line saying 
  168. whether the matched character is part of a tagged match word, and 
  169. if so, which one. After completing a line in this manner, it 
  170. passes through the line doing its replacements on the basis of 
  171. the flag array set on the first pass.
  172.  
  173. Finally, after the replace expression has built an output line, 
  174. that line is written to the standard output.
  175.  
  176. The operation of RPL can become deeply recursive when using 
  177. complex regular expressions, and its performance is quite 
  178. sensitive to the combination of expressions and input data. It is 
  179. not intended to be used for simple fixed string match and replace 
  180. due to the overhead of its generality.
  181.  
  182.  
  183. 3. Procedure Locator
  184.  
  185. ****  rpl.pas
  186.  
  187.   19   rpl(Input, Output);
  188.  120     parsecommand(usepsp : Boolean; cline : longstring);
  189.  129       writehelp;
  190.  417     getinputs;
  191.  426       realdiskfile(VAR fname : filestring; VAR useconsole : Boolean) : Boolean;
  192.  457       checkpat(pat : patline; VAR patrec : patptr) : Boolean;
  193.  605     processline(lin : line);
  194.  662     getfromfile;
  195.  726     writedebug;
  196.  
  197. ****  rpllow.inc
  198.  
  199.    8     hivid;
  200.   17     lovid;
  201.   26     initvid(VAR attribute : Byte; sethivid : Boolean);
  202.   46     resetvid(attribute : Byte);
  203.   60     Halt;
  204.   68     defaultextension(extension : filestring; VAR infile : filestring);
  205.   85     openfile(fname : filestring; VAR handle : Integer);
  206.  101     forcedup(handle, newhandle : Integer);
  207.  110     getchunk(VAR l : bufline; VAR count : Integer) : Boolean;
  208.  124     breakpressed : Boolean;
  209.  139     breakhalt;
  210.  149     setbreak;
  211.  158     createfile(fname : filestring; VAR handle : Integer);
  212.  175     closefile(handle : Integer);
  213.  188     iostat(bit : Integer) : Boolean;
  214.  203     time(VAR sec : Real);
  215.  211     appends(VAR l1; len1 : Integer; VAR l2; len2 : Integer; VAR lout : line);
  216.  239     checkmore(VAR screenline : Integer);
  217.  259     putl(l : line);
  218.  286     readyesno(default : Boolean) : Boolean;
  219.  302     getcom(usepsp : Boolean; inlin : longstring; VAR errstring : message) : Boolean;
  220.  317       comchar : Char;
  221.  
  222. ****  rplfind.inc
  223.  
  224.    8     foundfile(fname : filestring; VAR pathname : filestring;
  225.   33       getenvir(VAR ipath : Integer);
  226.   76       parsepath(ipath : Integer; VAR pathtop : Integer);
  227.   93       existremote(filename : longstring) : Boolean;
  228.  108       exist(VAR f : filetype) : Boolean;
  229.  117       openremote(pathname, fname : longstring; VAR f : filetype);
  230.  125         getcurrent(VAR cd : longstring; VAR drivenum : Integer);
  231.  146         changedrive(drivenum : Integer);
  232.  153         changedir(dirname : longstring);
  233.  
  234. ****  rplmat.inc
  235.  
  236.    8     match(VAR lin : line; pat : patptr) : Boolean;
  237.   14       amatch(VAR lin : line; offset : Integer; pat : patptr) : Integer;
  238.   23         omatch(VAR lin : line; VAR i : Integer; pat : patptr) : Boolean;
  239.  
  240. ****  rplpat.inc
  241.  
  242.    8     writepat(patrec : patptr);
  243.   42     getpat(VAR arg : patline; VAR patlist : patptr) : Boolean;
  244.   48       makepat(VAR arg : patline; start : Integer; delim : Char; VAR patlist : patptr) : Integer;
  245.   59         addpat(tok : tokens; lastj : patptr; VAR j : patptr; s : longstring);
  246.   63           cleanupcase(VAR s : longstring) : longstring;
  247.  109         getccl(VAR arg : patline; VAR i : Integer;
  248.  116           dodash(delim : Char; VAR arg : patline; VAR i : Integer; VAR s : longstring);
  249.  124             addstr(c : Char; VAR j : Integer; VAR s : longstring);
  250.  131             isalphanum(c : Char) : Boolean;
  251.  
  252. ****  rplrep.inc
  253.  
  254.    9     getrep(VAR arg : patline; VAR patlist : patptr) : Boolean;
  255.   13       makerep(VAR arg : patline; start : Integer; delim : Char; VAR patlist : patptr) : Integer;
  256.   22         addrep(tok : tokens; lastj : patptr; VAR j : patptr; s : longstring);
  257.   94     subline(VAR lin : line; patrec, reprec : patptr; VAR sub : line);
  258.  102       amatch(VAR lin : line; VAR flags : flag;
  259.  114         omatch(VAR lin : line; VAR flags : flag;
  260.  247       writesub(VAR lin : line; VAR flags : flag; reprec : patptr;
  261.  255         findtag(VAR lin : line; VAR flags : flag; i, iend, tagnum : Integer;
  262.  
  263.  
  264. 4. Hierarchy Diagram
  265.  
  266. rpl
  267.    resetvid, time, iostat, appends, initvid, setbreak
  268.    getinputs
  269.       forcedup, defaultextension
  270.       writepat
  271.          writepat
  272.       readyesno, realdiskfile
  273.       foundfile
  274.          getenvir, parsepath, existremote, exist
  275.          openremote
  276.             changedir, getcurrent, changedrive
  277.       parsecommand
  278.          forcedup, defaultextension, foundfile
  279.          parsecommand
  280.             halt
  281.                resetvid
  282.             getcom
  283.                comchar
  284.             openfile
  285.                halt
  286.             closefile
  287.                halt
  288.             writehelp
  289.                halt, hivid, lovid
  290.             getpat
  291.                makepat
  292.                   addpat
  293.                      cleanupcase, halt
  294.                   makepat
  295.                      getccl
  296.                         dodash
  297.                            isalphanum, addstr
  298.             getrep
  299.                makerep
  300.                   addrep
  301.                      halt
  302.       halt, getrep
  303.       checkpat
  304.          getpat
  305.       openfile
  306.       closefile
  307.       createfile
  308.          halt
  309.    writedebug
  310.       writepat
  311.    getfromfile
  312.       getchunk
  313.       processline
  314.          breakhalt, breakpressed, appends
  315.          match
  316.             amatch
  317.                amatch
  318.                   omatch
  319.                      amatch
  320.          putl
  321.             halt, appends
  322.             checkmore
  323.                halt
  324.          subline
  325.             amatch
  326.                amatch
  327.                   omatch
  328.                      amatch
  329.             appends
  330.             writesub
  331.                findtag, appends
  332.    parsecommand, putl, getcom
  333.    closefile
  334.  
  335.  
  336. 5. Special Features
  337.  
  338. A. Long Text Lines
  339.  
  340. RPL incorporates the same basic techniques that DIFF uses for 
  341. reading and writing long text lines (easily up to 32767 
  342. characters). See DIFF.DOC for details.
  343.  
  344. RPL treats long strings as records, with the length of the string 
  345. stored in an integer field and the text stored in a character 
  346. array. We provide a procedure APPENDS that allows you to append 
  347. these long strings and normal strings in any combination (always 
  348. creating a long string).
  349.  
  350. B. Treatment of Newlines
  351.  
  352. The Unix text matching tools possess an advantage over those that 
  353. must run within MSDOS and other operating systems. The end of 
  354. each text line in Unix is marked by a single character called 
  355. Newline. In MSDOS, each text line is terminated by a pair of 
  356. characters, Carriage Return and Line Feed. Although it seems 
  357. conceptually simple, matching these two characters as sometimes 
  358. one entity and sometimes individually turns into a major 
  359. headache.
  360.  
  361. You will find some tricky little pieces of code in the SUBLINE 
  362. procedure and in the two OMATCH functions that take care of these 
  363. problems. You can search for #13 (ASCII carriage return) to find 
  364. them. These code patches work well as long as <CR> and <LF> are 
  365. always found together, but you may be able to find some cases 
  366. where <LF> in the middle of a text line won't work. To "solve" 
  367. this we ignore <LF>s during the text read-in procedure and stick 
  368. a <CR><LF> pair onto the end of each line before pattern matching.
  369.  
  370. If you come up with more elegant solutions to these issues, 
  371. please let us know.
  372.  
  373.  
  374. 6. References
  375.  
  376. RPL's algorithms are modeled after, but upgraded from, those 
  377. presented in the following. The book also presents a somewhat 
  378. gentle introduction to regular expressions.
  379.  
  380.    Software Tools in Pascal, by B. Kernighan and P. Plauger, 
  381.    Addison-Wesley Publishing, 1981, pp. 141-168.
  382.  
  383. The basic idea for the record structure we use to represent match 
  384. tokens came from the following article, which provides a working 
  385. (although simplified) version of GREP written in C.
  386.  
  387.    "GREP.C", by Allen Holub, Dr. Dobbs Journal, October 1984, pp. 
  388.    50-56.
  389.  
  390. A more theoretical view of regular expressions and some different 
  391. (more powerful, and also more complicated) algorithms for 
  392. matching them is found in the following:
  393.  
  394.    Principles of Compiler Design, A. Aho and J. Ullman, Addison-
  395.    Wesley Publishing, 1979, pp. 74-118.
  396.  
  397. A user's introduction to regular expressions and GREP is given in 
  398. the following and in numerous other books about Unix:
  399.  
  400.    Introducing the Unix System, by H. McGilton and R. Morgan, 
  401.    McGraw-Hill Books, 1983, pp. 149-162.
  402.  
  403. And finally, if you have access to a Unix system, scan the MAN 
  404. entries for ED, SED, GREP, EGREP, and FGREP and also see if your 
  405. system has the EMACS text editor. Our utility RPL exceeds the 
  406. pattern matching capabilities of all of these tools with the 
  407. possible exception of EMACS.
  408.